package LeetCode.leetcode;

import domain.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 打印二叉树的所有路径
 * Created by 雷文康 on 2018/7/30.
 */
public class Test257二叉树的所有路径 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(5);
        root.left = node1;
        root.right = node2;
        node1.right = node3;
        List<String> result = binaryTreePaths2(root);
        for (String str : result) {
            System.out.println(str);
        }

    }

    //递归
    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.left == null && root.right == null) {
            result.add(root.val + "");
            return result;
        }

        int val = root.val;
        List<String> pathStr = new ArrayList<>();
        List<String> leftStr = binaryTreePaths(root.left);
        List<String> rightStr = binaryTreePaths(root.right);
        pathStr.addAll(leftStr);
        pathStr.addAll(rightStr);

        for (String str : pathStr) {
            result.add(val + "->" + str);
        }
        return result;
    }

    //非递归
    public static List<String> binaryTreePaths2(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (true) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {
                break;
            }
            node = stack.peek();
            if (isLeaf(node)) {
                addToResult(result, stack);

                stack.pop();
                TreeNode parent = stack.peek();
                while (parent.right == node || parent.right == null) {
                    node = stack.pop();
                    if (!stack.isEmpty()) {
                        parent = stack.peek();
                    } else {
                        break;
                    }
                }
                node = parent;
            }
            node = node.right;

        }

        return result;
    }

    private static boolean isLeaf(TreeNode node) {
        return node.right == null && node.left == null;
    }

    private static void addToResult(List<String> result, Stack<TreeNode> stack) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < stack.size(); i++) {
            sb.append(stack.elementAt(i) + "->");
        }
        result.add(sb.toString());
    }


}
